/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package dungeonsolver.controller.algorithm;

import dungeonsolver.helper.Utility;
import dungeonsolver.model.Labyrinth;
import java.awt.Point;
import java.awt.image.PixelGrabber;
import java.util.Vector;

/**
 *
 * @author LegACy
 */
public class AlgorithmBFS implements IAlgorithm {

	public Point[] getPath(Labyrinth labyrinth, Point from, Point to) {
		//Check
		if (labyrinth == null || from.equals(to)) return new Point[0];

		//Create visited map
		boolean[][] Map = labyrinth.getVisitMap();

		//Create variables
		int Depth			= 0;
		int MaxDepth		= 0;
		Point Current		= new Point(from);
		Vector<Point> Path	= new Vector<Point>();
		Vector<Point> Fork	= new Vector<Point>();

		//Log
		Utility.instance().addLog("Maximum depth is " + MaxDepth);

		//While not destination
		while (Current != null && (Current.x != to.x || Current.y != to.y)) {			
			//Set current position as visited
			Map[Current.x][Current.y] = true;

			//Get neighbors
			int ValidNeighbor = 0;
			Point[] Neighbors = labyrinth.getNeighbors(Current);
			for (int i = 0; i < Neighbors.length; i++) if (!Map[Neighbors[i].x][Neighbors[i].y]) ValidNeighbor++;

			//If a fork
			if (ValidNeighbor > 1) {
				//If doesn't exist
				if (Fork.isEmpty()) {
					//Add fork
					Fork.add(Current);
					Depth++;
				} else if (!Current.equals(Fork.lastElement())) {
					//Add fork
					Fork.add(Current);
					Depth++;
				}	
			}

			//Log
			Utility.instance().addLog("Arrived at [" + Current.x + "," + Current.y + "]... Depth: " + Depth);

			//For each neigbor
			int i		= 0;
			Point Next	= null;
			while (i < Neighbors.length && Next == null) {
				//If not visited, set as next
				if (!Map[Neighbors[i].x][Neighbors[i].y]) Next = Neighbors[i];

				//Next neighbor
				i++;
			}

			//Check depth and next
			if (Depth > MaxDepth || Next == null) {
				//Log
				if (Depth > MaxDepth) Utility.instance().addLog("Depth is more than maximum depth, stop checking current branch.");

				//If on fork
				if (Current.equals(Fork.lastElement())) {
					//Reduce fork
					Fork.remove(Fork.size() - 1);
					Depth--;
				}

				//If fork isn't empty, return there
				if (!Fork.isEmpty()) {
					Next = Fork.lastElement();

					//Remove paths
					while (!Path.isEmpty() && !Path.lastElement().equals(Next)) Path.removeElementAt(Path.size() - 1);
				}
				else {				
					//Increase max depth
					MaxDepth++;

					//Log
					Utility.instance().addLog("All branch has been checked, increase maximum allowed depth to " + MaxDepth + ".");

					//Reset
					Map		= labyrinth.getVisitMap();
					Depth	= 0;
					Next	= new Point(from);
					Path.removeAllElements();
					Fork.removeAllElements();
				}
			} else Path.add(Next);

			//Set as current
			Current = Next;
		}

		//Log
		Utility.instance().addLog("Arrived at [" + Current.x + "," + Current.y + "]... Destination encountered.");

		//Create array
		Point[] PathArray = new Point[Path.size()];
		for (int i = 0; i < PathArray.length; i++) PathArray[i] = Path.elementAt(i);

		//Return path
		return PathArray;
	}

}
